package edu.npu.GraphIndex;

import java.util.List;
import java.util.Map;
import java.util.Queue;

public //遍历的基类
class BasicGraphBFS {
	public Queue<Long> queue = null;
	public BasicGraphBFS() {
		
	}
	public BasicGraphBFS(Queue<Long> queue) {
		this.queue = queue;
	}
	//具体遍历的函数
	public void traverse(Map<Long, List<Long>> graph, Traversable traversedObj) {
		int level = 0;//遍历的层数
		long node = -1;//当前遍历的节点
		int levelSize = queue.size(), nextLevelSize = 0;//标记一层的边界
		while(!traversedObj.isDone(level)) {
			node = queue.poll();//弹出元素，表示已遍历
			levelSize--;
			traversedObj.action(node, level);
			
			for (long n : graph.get(node)) {
				if (!traversedObj.isTraversed(n) && !queue.contains(n)) {// 如果没有遍历并且没有在队列中的话就加入临接点
					queue.add(n);
					nextLevelSize++;
				}
			}
			
			//将层数处理放在这里,是为了使上一层的能够处理完,这样弹出的最后一个node也能得到处理
			if(levelSize == 0) {//到达了下一层
				level++;
				levelSize = nextLevelSize;
				nextLevelSize = 0;//归0，重新对下下层计数
			}
		}
	}
}
